/*
 * @lc app=leetcode.cn id=316 lang=cpp
 *
 * [316] 去除重复字母
 */

// @lc code=start
class Solution {
public:
    string removeDuplicateLetters(string s) {
        //贪心算法
        //存储一个当前结果序列
        //遍历原字符串,循环对比
        //如果遇到了比答案数组最后一位字典序小的
        //且最后答案序列的最后一个字母可以被删除时
        //就加入答案序列

        //last哈希表存储每个字母最后出现的次数
        unordered_map<char,int> last; 
        for(int i = 0; i < s.size(); i++)
            last[s[i]] = i;
        
        string temp;
        
        //存储答案序列字符是否出现
        //在新加入字母时，判断是否加入
        unordered_map<char,bool> vis;
        for(int i = 0; i < s.size(); i++){
            if(vis[s[i]] == true) continue;

            //删除答案序列末尾
            while(temp.size() != 0 && temp.back() > s[i] && last[temp.back()] > i){
                vis[temp.back()] = false;
                temp.pop_back();
            }

            temp += s[i];
            vis[temp.back()] = true;
        }
        
        return temp;
    }
};
// @lc code=end

